package Leetcode.图;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: kirito
 * @Date: 2024/9/7 16:40
 * @Description:
 * 给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，
 * 其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
 *
 * 请你返回 无法互相到达 的不同 点对数目 。
 *
 *
 * 输入：n = 3, edges = [[0,1],[0,2],[1,2]]
 * 输出：0
 * 解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。
 * 示例 2：
 *
 * 输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
 * 输出：14
 * 解释：总共有 14 个点对互相无法到达：
 * [[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
 * 所以我们返回 14 。
 */

public class 统计无向图中无法相互到达点对数 {
    /**
     * 建图后，用 DFS 可以求出每个连通块的大小。
     *
     * 求连通块的大小的同时，用一个变量 total 维护前面求出的连通块的大小之和。
     * 设当前连通块的大小为 size，那么这个连通块中的每个点，与前面遍历过的连通块的每个点，
     * 都是无法互相到达的，根据乘法原理，这有 size * total 个，加到答案中。
     * @param n 顶点数
     * @param edges 边
     * @return  统计无向图中无法相互到达点对数
     */
    public long countPairs(int n, int[][] edges) {
        List<Integer>[] graph = new ArrayList[n];
        Arrays.setAll(graph, e -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            graph[x].add(y);
            graph[y].add(x); // 建图
        }

        boolean[] visited = new boolean[n];
        long ans = 0;
        int total = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                // 未访问的点：说明找到了一个新的连通块
                //size表示dfs找到了一个连通块有size个点
                int size = dfs(i, graph, visited);
                ans += (long) size * total;
                total += size;
            }
        }
        return ans;
    }

    private int dfs(int i, List<Integer>[] graph, boolean[] visited) {
        //至少有当前的一个点
        int count = 1;
        visited[i] = true;
        //dfs
        for (int vertex : graph[i]) {
            if (!visited[vertex]) {
                count += dfs(vertex, graph, visited);
            }
        }
        return count;
    }
}
